/*
 * @lc app=leetcode.cn id=700 lang=java
 *
 * [700] 二叉搜索树中的搜索
 *
 * https://leetcode-cn.com/problems/search-in-a-binary-search-tree/description/
 *
 * algorithms
 * Easy (77.40%)
 * Likes:    227
 * Dislikes: 0
 * Total Accepted:    128.1K
 * Total Submissions: 165.5K
 * Testcase Example:  '[4,2,7,1,3]\n2'
 *
 * 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
 * 
 * 例如，
 * 
 * 
 * 给定二叉搜索树:
 * 
 * ⁠       4
 * ⁠      / \
 * ⁠     2   7
 * ⁠    / \
 * ⁠   1   3
 * 
 * 和值: 2
 * 
 * 
 * 你应该返回如下子树:
 * 
 * 
 * ⁠     2     
 * ⁠    / \   
 * ⁠   1   3
 * 
 * 
 * 在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。
 * 
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    // 中序迭代遍历 + 判断
    // public TreeNode searchBST(TreeNode root, int val) {
    //     Stack<TreeNode> stack = new Stack<>();
    //     TreeNode p = root;
    //     while (p != null || !stack.empty()) {
    //         if(p != null) {
    //             stack.push(p);
    //             p = p.left;
    //         } else {
    //             TreeNode treeNode = stack.pop();
    //             // 左孩子全部入栈后
    //             if (val == treeNode.val) {
    //                 return treeNode;
    //             }
    //             p = treeNode.right;   
    //         }
    //     }
    //     return null;
    // }

    // 迭代
    // public TreeNode searchBST(TreeNode root, int val) {
    //     while (root != null) {
    //         if (val == root.val) {
    //             return root;
    //         }
    //         root = val < root.val ? root.left : root.right;
    //     }
    //     return null;
    // }

    // 递归
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (val == root.val) {
            return root;
        } else {
            root = val < root.val ? root.left : root.right;
            return searchBST(root, val);
        }
    }

}

// @lc code=end

